Priority queues are utilized for a number of important computer-based applications. For example, worker threads of a large scale distributed computation may be configured to periodically retrieve the highest-priority task among the tasks currently placed in a prioritized work queue, remove the highest-priority task from the queue and perform the corresponding work operations. The tasks may be prioritized and placed into the work queues as needed by schedulers or task generators that operate independently of, and asynchronously with respect to, the worker threads. Such operational models may be used at various task granularities, from long-lasting data transfer jobs to medium-scale software development/deployment tasks to relatively short computations or analysis tasks.
The types of operations typically supported for priority queues may include, for example, queue creation and deletion, insertion of a new queue entry with a corresponding entry identifier and priority value, removal of an entry with a specified identifier, removal of an entry based on a priority criterion (e.g., an entry with the currently highest priority, or with a specified priority), and retrieval of entries based on various criteria for identifiers and/or priorities. Some queue-based applications may have additional requirements, such as cost constraints, consistency/integrity requirements, and the like.
A number of different underlying techniques may be used to implement priority queue mechanisms, depending, for example, on the infrastructure technologies (e.g., the various types of storage systems or database systems) available and the costs involved. In some naïve implementations of priority queues, the costs of doing some of the types of common queue operations (e.g., the number of reads and writes required for a given operation, which may translate directly or indirectly into client costs) may be dependent on the number of entries in the queue. For many applications, however, the number of entries that a given priority queue may have to hold is not easily predictable, and queue sizes may in some cases be expected to grow over time. In such scenarios, therefore, clients interested in priority queue services may wish to utilize implementations in which the costs of doing typical queue operations are low and, as far as possible, independent of the number of queue entries.
While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to.